import random
import gc

class BinaryBoard:
    # cell = []
    def __init__(self, rows, columns):
        self.rows = rows
        self.columns = columns
        self.state_0 = list(range(self.rows*self.columns))
        self.cell = []
        for i in range(self.rows*self.columns):
            self.cell.append(0)
        self.solution = []
    def __str__(self):
        if len(self.cell) == 0:
            return ""
        string = ""
        for i in range(self.rows):
            for j in range(self.columns):
                string += str(self.cell[i*self.columns+j]) + ' '
            string = string[:-1] + '\n'
        return string[:-1]
        
    def renew(self):
        self.cell = []
        for i in range(self.rows*self.columns):
            self.cell.append(0)
        self.solution = []
        self.state_0 = list(range(self.rows*self.columns))
        max_value = max(self.rows, self.columns) + 1
        random.seed()
        while self.state_0:
            target = random.choice(self.state_0)
            if self.cell[target] == 0:
                self.toggle(target)
            # print(self, '\n')
            # breakpoint()
        self.solution.sort()
        del self.state_0
        gc.collect()
    def toggle(self, index):
        if self.check_diagonal(index):
            self.toggle_marked(index)
            self.toggle_adjacent(index)
            self.toggle_diagonal(index)
    def toggle_marked(self, index):
        self.cell[index] = 1
        self.solution.append(index)
        self.state_0.remove(index)
    def toggle_safe(self, index):
        self.cell[index] = 2
        self.state_0.remove(index)
    def toggle_adjacent(self, index):
        for i in {2,4,6,8}:
            target = self.get_position(index, i)
            if target >= 0:
                if self.cell[target] == 0:
                    self.toggle_safe(target)
    def toggle_diagonal(self, index):
        for i in {1,3,7,9}:
            target = self.get_position(index, i)
            if target >= 0:
                if self.cell[target] == 0:
                    self.check_diagonal(target)
    def check_adjacent(self, index):
        for i in {2,4,6,8}:
            target = self.get_position(index, i)
            if target >= 0:
                if self.cell[target] == 1:
                    return False
        return True
    def check_diagonal(self, index):
        if self.is_border(index):
            ct = 1
        else:
            ct = 0
        for i in {1,3,7,9}:
            target = self.get_position(index, i)
            if target >= 0:
                if self.cell[target] == 1:
                    ct += self.check_border(target, i, index)
                    if ct > 1:
                        self.toggle_safe(index)
                        return False
        return True
    # def check_diagonal(self, index, type, source):
        # ct = 0
        # for i in {1,3,7,9}.difference({10-type}):
            # target = self.get_position(index, i)
            # if target == source:
                # return 2
            # if target == 1:
                # self.check_diagonal(target, i, source)
    def check_border(self, index, type, source):
        if self.is_border(index):
            return 1
        ct = 0
        for i in {1,3,7,9}.difference({10-type}):
            target = self.get_position(index, i)
            if target == source:
                # breakpoint()
                return 2
            if self.cell[target] == 1:
                ct += self.check_border(target, i, source)
                if ct > 1:
                    break
        return ct
        
    def get_position(self, index, type):
        if type < 5:
            if type < 3:
                if type == 1:
                    if self.is_top(index) or self.is_left(index):
                        return -1
                    else:
                        return index - self.columns - 1
                elif type == 2:
                    if self.is_top(index):
                        return -1
                    else:
                        return index - self.columns
            else:
                if type == 3:
                    if self.is_top(index) or self.is_right(index):
                        return -1
                    else:
                        return index - self.columns + 1
                elif type == 4:
                    if self.is_left(index):
                        return -1
                    else:
                        return index - 1
        else:
            if type < 8:
                if type == 6:
                    if self.is_right(index):
                        return -1
                    else:
                        return index + 1
                elif type == 7:
                    if self.is_left(index) or self.is_bottom(index):
                        return -1
                    else:
                        return index + self.columns - 1
                else:
                    return index
            else:
                if type == 8:
                    if self.is_bottom(index):
                        return -1
                    else:
                        return index + self.columns
                elif type == 9:
                    if self.is_right(index) or self.is_bottom(index):
                        return -1
                    else:
                        return index + self.columns + 1
    def is_top(self, index):
        return index < self.columns
    def is_bottom(self, index):
        return index >= self.columns*(self.rows-1)
    def is_left(self, index):
        return index % self.columns == 0
    def is_right(self, index):
        return self.is_left(index+1)
    def is_border(self, index):
        return self.is_top(index) or self.is_bottom(index) or self.is_left(index) or self.is_right(index)
    def is_solved(self):
        for i in self.cell:
            if i == 0:
                return False
        return True